"""
https://leetcode.cn/problems/permutations/description/

46. 全排列
已解答
中等
相关标签
相关企业
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

 

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：

输入：nums = [1]
输出：[[1]]
 

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

"""
from typing import List, Set


class Solution:
    """
    考虑使用递归方式
    另一种方案，考虑nums的每个元素，在结果集中必定有自己的一个位置。
    而我们的目的，就是寻找每个元素在不同位置的所有可能性。

    已解决但效率不算太高
    """
    def permute(self, nums: List[int]) -> List[List[int]]:
        
        def calc(before_nums_arr:List[List[int]],last_nums:Set[int])->List[List[int]]:
            if len(last_nums)==0:
                return before_nums_arr
            # 对每个before_nums_arr的数组进行相同的处理
            all_nums_arr=[]
            for num in last_nums: 
                new_last_nums=last_nums.copy()
                new_last_nums.remove(num)
                new_before_nums_arr=[]
                for before_nums in before_nums_arr:
                    res=before_nums.copy()
                    res.append(num)
                    new_before_nums_arr.append(res)
                    
                res=calc(new_before_nums_arr, new_last_nums)
                all_nums_arr.extend(res)
            return all_nums_arr
                    
        final_res=calc([[]],set(nums))
        return final_res

if __name__=='__main__':
    s=Solution()
    nums=[1]
    res_list=s.permute(nums)
    for result in res_list:
        print(result)
    pass